795. Number of Subarrays with Bounded Maximum
Medium

We are given an array nums of positive integers, and two positive integers left and right (left <= right).

Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least left and at most right.

Example:
Input: 
nums = [2, 1, 4, 3]
left = 2
right = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].

Note:

  • left, right, and nums[i] will be an integer in the range [0, 109].
  • The length of nums will be in the range of [1, 50000].
Accepted
37,273
Submissions
73,139
Seen this question in a real interview before?
Companies
Related Topics

Average Rating: 4.22 (32 votes)

Premium

Approach #1: Counting [Accepted]

Intuition

We can make the following logical steps to arrive at the solution:

As we only care about whether each element is less than, between, or greater than the interval [L, R], let's pretend each element is either 0 if it is less than L; 1 if it is between L and R; or 2 if it is greater than R.

Then, we want the number of subarrays with no 2 and at least one 1. The 2s split the array into groups of arrays with only 0s and 1s. For example, if our array is [0, 0, 1, 2, 2, 1, 0, 2, 0], then the answer is just the answer for [0, 0, 1] plus the answer for [1, 0] plus the answer for [0].

For each such group (arrays of only 0s or 1s), to count the number of subarrays that have at least one 1, let's count all the subarrays in the group, minus the subarrays that only have zeroes.

For example, [0, 0, 1] has 6 subarrays, 3 of which are zero-only, which adds 3 to the answer; [1, 0] has 3 subarrays, 1 of which is zero-only, which adds 2 to the answer; and [0] has 1 subarray, 1 of which is zero-only, which adds 0 to the answer. The final answer to the previous original example of A = [0, 0, 1, 2, 2, 1, 0, 2, 0] is 3 + 2 + 0 = 5.

Algorithm

Say count(B) is the number of subarrays that have all elements less than or equal to B. From the above reasoning, the answer is count(R) - count(L-1).

How do we compute count(B)? We remember cur, the number of contiguous, previous elements less than or equal to B. When we see a new element less than or equal to B, the number of valid subarrays ending at this position is cur + 1. When we see a new element greater than B, the number of valid subarrays ending at this position is 0.

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the length of A.

  • Space Complexity: O(1)O(1).

Report Article Issue

Comments: 9
virtyaluk's avatar
Read More

Paid subscription doesn't worth it just because of the articles like this one. You will find much better solutions in the discussion section.

7
Show 2 replies
Reply
Share
Report
henrya2's avatar
Read More

I don't understand why count(B) will work?

3
Reply
Share
Report
acbthisisit's avatar
Read More

This is such a deceptive problem . At first looks like an Easy Sliding window, but is actually a hard one

2
Reply
Share
Report
morelikefreeshirt's avatar
Read More

cool math proof

1
Reply
Share
Report
mycoding1729's avatar
Read More

It's better to include the dp approach where dp[i] = number of valid subarrays ending with i. And then based on 3 cases perform the dp update:
if arr[i] < left => dp[i] = dp[i-1]
else if arr[i] > right => dp[i] = 0, prev = i // initially previous will be -1
else dp[i] = i-prev

Finally answer is sum of all dp[i];

1
Reply
Share
Report
henrya2's avatar
Read More

ans += cur; is so weird.
I don't know how to figure it out. And there is no explanation for this.

0
Show 3 replies
Reply
Share
Report
sidhara's avatar
Read More

I solved the question using backtracking , complexity is like real bad but got accepted.
Still trying to learn dp so here's my take on it.

class Solution {
    int solution =0;
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
       /* Adding the max element to know wether we already have an element in the array and 
that element value is >= left and <= right*/
        backTrack(nums,left,right,0,Integer.MIN_VALUE);
        return solution;
    }
    
    
    public void backTrack(int[] nums, int left, int right,int index,int max)
    {
        
        if(max>= left && max <=right)
            solution++;
        
        for(int i=index;i<nums.length;i++)
        {
            if((nums[i] >= left && nums[i]<=right) || nums[i]<left)
            {
                backTrack(nums,left,right,i+1,Math.max(max,nums[i]));
                /* this is to break when we come out of array such as 
                   for {2,1,3,4}  [2,1] is an array but once it backtracks, removes 1 
                    and tries to add 3 to form [2,3], the below condition would truncate the flow*/
                if(max!=Integer.MIN_VALUE)
                    break;
            }
          /* for Example {2,1,3,4} left =2, right=3 here we are breaking if we try to add 4 to an existing array, 
             if the array is empty then we will move to the next element in the array */
            else if(nums[i] > right && max!=Integer.MIN_VALUE)
                break;
            else
                continue;
        }
    }
}

Complexity is quite bad, just wanted to add a different way to do the problem.

0
Reply
Share
Report
SoloZ's avatar
Read More

Just read the Algorithm section makes more sense to me:

Find the number of subarrays count(R) whose maximum element is no larger than R and similarly count(L-1).

count(R) - count(L-1) by definition is the number of subarrays whose max is between L and R inclusive.

0
Reply
Share
Report
cxhcxh's avatar
Read More

This question could be Hard
Count of Subarrays in range (L, R] => Count of Subarrays at most R - Count of Subarrays at most L
Similar questions:
1248:

public int numberOfSubarrays(int[] A, int K) {
       return atMostK(A, K) - atMostK(A, K - 1);
    }
    
    private int atMostK(int[] A, int K) {
        int ans = 0;
        int count = 0;
        for(int l = 0, r = 0; r < A.length; r++) {
            count += A[r] % 2;
            while(count > K) {
                count -= A[l] % 2;
                l++;
            }
            ans += r - l + 1;
        }
        return ans;
    }

992:

public int subarraysWithKDistinct(int[] A, int K) {
       return atMostK(A, K) - atMostK(A, K - 1);
    }

    private int atMostK(int[] A, int K) {
        int ans = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0, j = 0; j < A.length; j++) {
            map.put(A[j], map.getOrDefault(A[j], 0) + 1);
            
            while(map.size() > K) {
                int count = map.get(A[i]);
                if(count == 1) map.remove(A[i]);
                else map.put(A[i], count - 1);
                i++;
            }
            
            ans += j - i + 1;
        }
        return ans;
    }

0
Show 1 reply
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.